1. Field of the Invention
This invention relates to caching arrangements used in computer systems and, more particularly, to methods and apparatus for caching data expected to be used by such systems.
2. History of the Prior Art:
In computer systems, the access of main memory to retrieve information often takes a substantial portion of the operational time. This occurs for various reasons. First, main memory is random access memory which is often sufficiently large that its cost is kept within bounds by using relatively slow memory devices. Second, in systems using virtual memory arrangements to increase the addressable space without increasing the physical size of the main memory, it is necessary to address information in both main memory and secondary memory such as magnetic disk storage by means of memory management arrangements which utilize look-up tables to translate virtual addresses to physical addresses. This indirect addressing requires a substantial amount of time.
For this reason, the use of cache memories to increase system speed has become prevalent in more advanced systems. A cache memory makes use of a relatively small amount of fast (and therefore expensive) random access memory in which recently used instructions, data, or both are stored as they are used by a processor. Such information is then available in the cache memory so that it may be more rapidly accessed by the associated processor when next required. The basic theory of caching is that, in general, information which has been recently used is more likely to be used sooner than is other information. The cache memory is often both physically faster than the random access memory used for main memory and is arranged so that it may be addressed more rapidly than may main memory by obviating the need for the look-up operation to determine physical addresses. Such caching arrangements have operated to greatly increase the speed of operation of computer systems for certain types of information.
Caching works well in situations where the same information is repeatedly utilized in carrying out an operation. An example of such a use is found in executing an instruction including a looping operation. Caching does not usually work well in situations in which entirely new information is used in each step of the operation. For example, in scrolling down the screen of a computer output display which shows approximately one thousand pixels of eight bit bit-mapped color information in each of the horizontal and vertical directions, approximately one megabyte of data is traversed. A typical cache memory may hold sixty-four kilobytes of information. A scrolling operation essentially reads information in a first scan line and writes that information to the next line below or above. When the cache is used to accomplish scrolling, it can hold only a few lines from such a frame buffer. Thus, except for the first few lines, none of the information which has been placed in the cache memory is reused so no increase in speed is accomplished. Moreover, since for the greatest part of the scrolling operation the processor is continually filling the cache memory with new information, the operation takes much longer using a cache memory than it would without a cache memory. In such a cache fill operation, the processor must first look to the cache memory for the information, determine that the information is missing in the cache memory, go to the look-up tables for the physical address of the information, access the information to be used in main memory, store that information in the cache memory replacing other information, and finally use the information. Such an operation must repeat continuously during a scrolling operation so that the fact that the operation takes longer than a simple access of main memory should not be surprising.
One method of increasing the speed of operation of a computer is to design the processor to handle instructions which are pipelined so that one instruction is executed during each clock cycle of operation. While the early pipelined computer systems using caching demonstrated a loss of approximately four instructions for each cache memory miss, the faster systems being designed at present will have a loss of as much as sixty-four instruction times for each cache miss. This is a very large delay in a fast computer system. For this reason, many systems now include methods for disabling the caching operation in situations in which it may delay the operation of the system. Although such methods eliminate the delays caused by the caching of certain information, they do not speed the handling of that information in any other way.